Relation d'équivalence

Propriété

Soit $a,b\in \mathbb{Z}$ et $n\in {\mathbb{N}}^{\ast }$ . On a les trois propriétés suivantes.

• Réflexivité : $a\equiv a[n]$ .
• Symétrie : si $a\equiv b[n]$ , alors $b\equiv a[n]$ .
• Transitivité : si $a\equiv b[n]$ et $b\equiv c[n]$ , alors $a\equiv c[n]$ .

On dit que la relation de congruence modulo $n$ est, comme la relation d'égalité, une relation d'équivalence. La propriété de symétrie permet de parler d'entiers $a$ et $b$  congrus modulo $n$ .

Démonstration

• $a-a=0$ est un multiple de $n$ ( $0=n\times 0$ ), donc $a\equiv a[n]$ .
• Si $a\equiv b[n]$ , alors $a-b$ est un multiple de $n$ , donc il existe $k\in \mathbb{Z}$ tel que $a-b=kn$ . On a donc $b-a=-kn=k^{\prime }n$ avec $k^{\prime }=-k\in \mathbb{Z}$ . Ainsi, $b-a$ est un multiple de $n$ et donc $b\equiv a[n]$ .
• Si $a\equiv b[n]$ et $b\equiv c[n]$ , alors il existe $k,k^{\prime }\in \mathbb{Z}$ tels que $a-b=kn$ et $b-c=k^{\prime }n$ . On a alors :   $a-c=a-b+b-c=kn+k^{\prime }n=(k+k^{\prime })n=k^{″}n$  avec $k^{″}=k+k^{\prime }\in \mathbb{Z}$ . Ainsi, $a-c$ est est un multiple de $n$ et donc $a\equiv c[n]$ .

Exemple

Grâce à la transitivité, on peut écrire des congruences en chaîne.
Par exemple : $23\equiv 44\equiv 30\equiv 16\equiv 9\equiv -12\equiv 2\equiv -5[7]$ .